"""
⼆分查找⽤于在有序数组中查找元素，通过反复将搜索范围缩⼩⼀半来找到⽬标元素。
"""
def binary_search(nums, target):
    left = 0     #左边指针
    right = len(nums)-1  #右边指针

    for i in range(len(nums)//2): #循环次数不超过数组长度的一半，但只要超过数组长度的一半都可，循环在返回None的时候不执行多余部分
        mid = (left + right) // 2 #求中间的位置
        if target < nums[mid]:      #如果中间值比目标值小，则将右边指针移到中间位置的左边
            right =mid-1

        if target > nums[mid]:      #如果中间值比目标值大，则将左边指针移到中间位置的右边
            left = mid+1

        if target == nums[mid]:     #如果中间值等于目标值，则返回中间位置
            return mid

        if left > right:    #如果左边指针比右边指针大，则说明没有找到目标值
            return None


list = [1,2,3,4,5,6,7,8,9]
print(binary_search(list, 11))